package com.yc.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class StringHandle {
    public static void main(String[] args) {
        StringHandle s = new StringHandle();
//        System.out.println(s.reverseVowels("leetcode"));
//        System.out.println(s.reverseWords("the sky is blue"));
//        System.out.println(s.reverseWords("  hello world  "));
//        System.out.println(s.reverseWords("a good   example"));
//        s.m1();
//        s.m2();
        s.m3();
//        s.cover();
    }
    public String reverseVowels(String s) {
        if (s.length() < 2) {
            return s;
        }

        char[] sa = s.toCharArray();
        int pre = 0;int end = sa.length-1;
        char c = 'a';
        while(pre < end) {
            if(!isY(sa[pre])) {
                pre++;
                continue;
            }
            if(!isY(sa[end])) {
                end--;
                continue;
            }
            if (pre < end) {
                c = sa[pre];
                sa[pre] = sa[end];
                sa[end] = c;
                pre++;end--;
            }
        }

        return new String(sa);
    }

    boolean isY(char c) {
        return c=='a' || c=='e' || c=='i' || c=='o' || c=='u' ||
                c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
    }

    public String reverseWords(String s) {
        StringBuffer res = new StringBuffer();
        StringBuffer item = new StringBuffer();

        for (int i=s.length()-1; i>=0;) {
            if (s.charAt(i) != ' ') {
                item.insert(0, s.charAt(i));
                i--;
            } else {
                int flag = 1;
                while(i > 0 && s.charAt(i) == ' ') {
                    i--;
                    flag = 0;
                }
                i -= flag;
                if (res.length() != 0 || item.length() != 0) {
                    if (res.length() != 0 && item.length() != 0) {
                        res.append(" ");
                    }
                    res.append(item);
                    item.setLength(0);
                }
            }
        }
        if (item.length() > 0) {
            if (res.length() != 0) {
                res.append(" ");
            }
            res.append(item);
        }

        return res.toString();
    }

    public void m1() {
        int[] a = {1,2,3,4};
        productExceptSelf(a);
    }

    public int[] productExceptSelf(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i=0; i<nums.length; i++) {
            dp[i] = (i==0)?1:(dp[i] * dp[i-1] * nums[i-1]);
            dp[nums.length-1-i] = (i==0)?1:(dp[nums.length-1-i] * dp[nums.length-i] * nums[nums.length-i]);
        }
        return dp;
    }

    public void m2() {
        int[] a = {1,2,3,4,5};
        System.out.println(increasingTriplet(a));

    }

    public boolean increasingTriplet(int[] nums) {
        List<Integer[]> tmp = new ArrayList<>();
        for(int i=0; i<nums.length; i++) {
            if (tmp.isEmpty()) {
                tmp.add(new Integer[3]);
            }
            for (int j=0; j<tmp.size(); j++) {
                Integer[] a = tmp.get(j);
                for (int k=0; k<3; k++) {
                    if (a[k] == null) {
                        if (k==0) {
                            a[0] = nums[i];
                        } else {
                            if (a[k-1] < nums[i]) {
                                a[k] = nums[i];
                                if (k==2) {
                                    return true;
                                }
                            } else {
                                if (k ==1) {
                                    a[0] = nums[i];
                                } else if (k==2) {
                                    if (nums[i] > a[0]) {
                                        a[1] = nums[i];
                                    } else {
                                        tmp.add(new Integer[3]);
                                        tmp.get(tmp.size()-1)[0] = nums[i];
                                    }
                                }
                            }
                        }
                        break;
                    }
                }
            }

        }
        return false;
    }

    /**
     * 十进制转2进制
     */
    public void m3() {
//        System.out.println(to2_1(0));
//        System.out.println(to2_1(1));
//        System.out.println(to2_1(2));
//        System.out.println(to2_1(5));

//        System.out.println(to2_2(5));
//        System.out.println(binaryToDecimal2(5));
        countBits(2);
    }

    /**
     * 用数学方式：除以2 取余
     * 有局限性：负数是用补码形式存储。如果拿掉负号，按整数处理，处理出来的其实是"原码"
     * 算法注意点：没想到还是要用递归，因为处理到最后总能到1，或者0.或者从一开始就是0，1
     * @param num
     * @return
     */
    public String to2_1(int num) {
        StringBuffer sb = new StringBuffer();
        to2_1_2(num, sb);
        return sb.toString();
    }

    public void to2_1_2(int num, StringBuffer res) {
        if(num < 2) {
            res.insert(0, num);
        } else {
            res.insert(0, num%2);
            to2_1_2(num/2, res);
        }
    }
    //非递归方式
    public void binaryToDecimal(int n){
        String str = "";
        while(n!=0){
            str = n%2+str;
            n = n/2;
        }
        System.out.println(str);
    }

    /**
     * 用取余方式
     * 没有什么局限性。用的就是计算机的存储结构。会原模原样的输出计算机内部的存储结构
     * @param num
     * @return
     */
    public String to2_2(int num) {
        StringBuilder sb = new StringBuilder();//StringBuilder是线程不安全的，可以提高性能
        sb.append(binaryToDecimal2(1<<31));//左移31位，是可以覆盖符号位的。
        // >>>的意思是：即便是负数，左边也照样补0，而不是补1。之所以没有<<<，因为没有意义，<<<将和<<意思一样
//        StringBuffer sb = new StringBuffer();
//        sb.append("0");
//        for (int i=30; i>=0; i--) {
//            sb.append(num & (1 << i));//把1左移，是错误的想法，因为左移了之后，右边空出来的0都是有意义的
//        }
        Integer.toBinaryString(num);//Integer本质上用的是"数学方式"：除以2取余。为的是通用性：可以处理转成任意进制
        return sb.toString();
    }


    public String binaryToDecimal2(int n){
        StringBuffer sb = new StringBuffer();
        for(int i = 31;i >= 0; i--) {
            sb.append(n >>> i & 1);
        }
        return sb.toString();
    }

    /**
     * 通过位运算交换两个数
     */
    public void cover() {
        int a = 2;
        int b = 2;

        a = a^b;
        b = b^a;
        a = a^b;

        System.out.println("a=" + a);
        System.out.println("b=" + b);
        List<String> asss = new ArrayList<>();

//        a = a^a^a;
//        System.out.println("a=" + a);
//        HashMap m = new HashMap();
    }

    public int[] countBits(int n) {
        //求二进制中1的个数
        StringBuffer sb = new StringBuffer();
        int count = 0;
        for (int i=31; i>=0; i--) {
            sb.append(n >>> i & 1);
            if ((n >>> i & 1) == 1) {
                count++;
            }
        }
        System.out.println("count:" + count);
        //将个数转化为二进制
        int[] res = new int[n+1];
        for (int i=0; i<n+1; i++) {
            res[i] = (count>>i)&1;
        }
        return res;

    }

}
